use std::fmt::{Debug};
use std::ops::{IndexMut};
use std::default::{Default};
use diff;

/// Abstraction for the underlying tree to render changes onto.
pub trait Underlying: IndexMut<usize, Output=Self> + Sized + diff::ApplyPatch<Self> {
  type Spine: Eq + Clone + Debug;
  type Info;

  fn create(spine: Self::Spine, info: Self::Info, children: Vec<Self>) -> Self;
  fn set_spine(&mut self, spine: Self::Spine);
  fn set_info(&mut self, info: Self::Info);
}

////////////////////////////////////////////////////////////////////////////////////////////////////

/// Virtual tree -- specifies how the tree should look. Components will return these in their render
/// functions, and that will be used to apply any changes to the live tree (below).
#[derive(Clone, Debug, Eq, PartialEq)]
enum Virt<U: Underlying> {
  Frag(U),
  Branch(VirtBranch<U>, U::Info),
}

/// Live tree -- specifies the current shape of the tree with any additional state attached to
/// nodes.
#[derive(Debug, Eq, PartialEq)]
enum Live<U: Underlying> {
  Frag,
  Branch(LiveBranch<U>, usize),
}

#[derive(Clone, Debug, Eq, PartialEq)]
struct Branch<U: Underlying, A> {
  spine: U::Spine,
  arms: Vec<A>,
}

type VirtBranch<U> = Branch<U, Virt<U>>;
type LiveBranch<U> = Branch<U, Live<U>>;

/// Generic structure for result of comparing trees. The reason it has so many type parameters is
/// that the values within differ greatly base on if the comparison takes ownership or not. See the
/// `LiveVirtCmp` and `LiveVirtCmpMut` variations below.
#[derive(Debug)]
enum Cmp<D, B1, B2, I, F> {
  Different(D), // different spines
  Branch(B1, B2, I), // both trees are Branch; RHS has info I
  Frag(F), // both trees are Frag; RHS has fragment F
}

type LiveVirtCmp<'a, U> =
  Cmp<(),
      &'a Branch<U, Live<U>>,
      &'a Branch<U, Virt<U>>,
      &'a <U as Underlying>::Info,
      &'a U>;

type LiveVirtCmpMut<'a, U> =
  Cmp<Virt<U>,
      &'a mut Branch<U, Live<U>>,
      Branch<U, Virt<U>>,
      <U as Underlying>::Info,
      U>;

////////////////////////////////////////////////////////////////////////////////////////////////////

impl<U> From<U> for Virt<U> where U: Underlying {
  fn from(frg: U) -> Self {
    Virt::Frag(frg)
  }
}

impl<U> From<LiveBranch<U>> for Live<U> where U: Underlying {
  fn from(b: LiveBranch<U>) -> Self {
    Live::Branch(b, 0)
  }
}

impl<U: Underlying> Virt<U> {
  /// Build an actual tree (live and underlying) from this virtual tree. The resulting
  /// trees are in sync.
  fn build(self) -> (Live<U>, U) {
    match self {
      Virt::Frag(frg) =>
        (Live::Frag, frg),

      Virt::Branch(Branch { spine, arms }, info) => {
        let (arms, u_arms) =
          arms.into_iter()
              .map(Virt::build)
              .unzip();
        (Branch { spine: spine.clone(), arms }.into(),
         U::create(spine, info, u_arms))
      }
    }
  }
}

impl<U: Underlying> Live<U> {
  /// Compare trees shallowly.
  fn compare<'a>(&'a self, virt: &'a Virt<U>) -> LiveVirtCmp<'a, U> {
    match *self {
      Live::Branch(ref b, _) =>
        match *virt {
          Virt::Branch(ref vb, ref i) => Cmp::Branch(b, vb, i),
          _ => Cmp::Different(()),
        }

      Live::Frag =>
        match *virt {
          Virt::Frag(ref u) => Cmp::Frag(u),
          _ => Cmp::Different(()),
        }
    }
  }

  /// Compare trees shallowly (mutable; takes ownership of RHS).
  fn compare_mut(&mut self, virt: Virt<U>) -> LiveVirtCmpMut<U> {
    match *self {
      Live::Branch(ref mut b, _) =>
        match virt {
          Virt::Branch(vb, info) => Cmp::Branch(b, vb, info),
          _ => Cmp::Different(virt),
        }

      Live::Frag =>
        match virt {
          Virt::Frag(u) => Cmp::Frag(u),
          _ => Cmp::Different(virt),
        }
    }
  }

  /// Impose a structure of a virtual tree onto this live tree, updating this tree so that it
  /// matches, and bringing the underlying tree up to sync as well.
  fn impose(&mut self, virt: Virt<U>, underly: &mut U) {
    match self.compare_mut(virt) {
      Cmp::Branch(b, vb, info) => {
        if b.spine != vb.spine {
          b.spine = vb.spine.clone();
          underly.set_spine(vb.spine.clone());
        }
        underly.set_info(info);
        diff_vecs(&mut b.arms, vb.arms, underly);
        self.incr_counter();
      }

      Cmp::Frag(f) => {
        *self = Live::Frag;
        *underly = f;
      }

      Cmp::Different(virt) => {
        let (new_live, new_underly) = virt.build();
        *self = new_live;
        *underly = new_underly;
      }
    }
  }

  fn incr_counter(&mut self) -> &mut Self {
    match *self {
      Live::Branch(_, ref mut n) => *n = n.saturating_add(1),
      _ => (),
    }
    self
  }
}

fn diff_vecs<'a, U>(lives: &'a mut Vec<Live<U>>,
                    virts: Vec<Virt<U>>,
                    base_underlying: &'a mut U)
where U: Underlying + 'a {
  let patch = diff::gen(lives, virts);
  diff::ApplyPatch::apply_patch(
    &mut TreeApplyPatch { lives, base_underlying },
    patch,
  ).unwrap()  // *shouldn't* fail!!
}

impl<U: Underlying> diff::Cmp<Virt<U>> for Live<U> {
  fn similar(&self, virt: &Virt<U>) -> bool {
    match self.compare(virt) {
      Cmp::Branch(b1, b2, _) => {
        // print!("compare spines: {:?} = {:?} ({})\n", b1.spine, b2.spine, b1.spine == b2.spine);
        b1.spine == b2.spine
      }
      Cmp::Frag(_) => true,
      Cmp::Different(()) => false,
    }
  }
}

/// Helper struct for implementing diff::ApplyPatch. Patches applied to this structure will be
/// applied to both 'lives' and 'base_underlying'. In particular, `overwrite()` will call
/// `.impose()` rather than naively overwriting nodes in the tree.
struct TreeApplyPatch<'a, U: Underlying + 'a> {
  lives: &'a mut Vec<Live<U>>,
  base_underlying: &'a mut U,
}

impl<'a, U: Underlying> diff::ApplyPatch<Virt<U>> for TreeApplyPatch<'a, U> {
  fn len(&self) -> usize { self.lives.len() }

  fn remove(&mut self, i: usize) {
    self.lives.remove(i);
    self.base_underlying.remove(i);
  }

  fn insert(&mut self, i: usize, v: Virt<U>) {
    let (live, under) = v.build();
    self.lives.insert(i, live);
    self.base_underlying.insert(i, under);
  }

  fn overwrite(&mut self, i: usize, v: Virt<U>) -> bool {
    self.lives[i].impose(v, &mut self.base_underlying[i]);
    true
  }
}


////////////////////////////////////////////////////////////////////////////////////////////////////

#[cfg(test)]
mod test {
  use super::*;
  use diff;
  use std::ops::{Index, IndexMut};

  #[derive(Clone, Eq, PartialEq, Debug)]
  struct StrT {
    spine: String,
    children: Vec<StrT>,
  }

  /// Helper to succinctly create trees.
  fn parse<B, A, I, T>(i: &mut I, build: &B, alt: &A) -> Option<T>
  where I: Iterator<Item=char>,
        B: Fn(String, Vec<T>) -> T,
        A: Fn() -> T {
    let mut spine = String::from("");
    loop {
      match i.next().unwrap() {
        ')' => return None,
        '*' => return Some(alt()),
        '(' => break,
        c => spine.push(c),
      }
    }
    let mut arms = Vec::new();
    loop {
      match parse(i, build, alt) {
        Some(e) => arms.push(e),
        None => return Some(build(spine, arms)),
      }
    }
  }

  fn tree(s: &str) -> StrT {
    parse(&mut s.chars(), &|spine, children| StrT { spine, children }, &|| panic!(".")).unwrap()
  }

  fn live(s: &str) -> Live<StrT> {
    parse(&mut s.chars(), &|spine, arms| Branch { spine, arms }.into(), &|| Live::Frag).unwrap()
  }

  fn virt(s: &str) -> Virt<StrT> {
    parse(&mut s.chars(),
          &|spine, arms| Virt::Branch(Branch { spine, arms }, ()),
          &|| Virt::Frag(tree("alt()"))).unwrap()
  }

  #[test]
  fn test_parse() {
    assert_eq!(tree("3(1()2())"),
               StrT { spine: "3".into(),
                      children: vec![
                        StrT { spine: "1".into(), children: vec![] },
                        StrT { spine: "2".into(), children: vec![] },
                      ] });
    assert_eq!(live("3(1()*)"),
               Branch { spine: "3".into(),
                        arms: vec![
                          Branch { spine: "1".into(), arms: vec![] }.into(),
                          Live::Frag,
                        ] }.into());
  }

  impl Index<usize> for StrT {
    type Output = StrT;
    fn index(&self, i: usize) -> &StrT {
      &self.children[i]
    }
  }

  impl IndexMut<usize> for StrT {
    fn index_mut(&mut self, i: usize) -> &mut StrT {
      &mut self.children[i]
    }
  }

  impl Underlying for StrT {
    type Spine = String;
    type Info = ();

    fn create(spine: String, _: (), children: Vec<StrT>) -> Self {
      StrT { spine, children }
    }

    fn set_spine(&mut self, spine: String) {
      self.spine = spine;
    }

    fn set_info(&mut self, _: ()) {}
  }

  impl diff::ApplyPatch<StrT> for StrT {
    fn len(&self) -> usize {
      self.children.len()
    }

    fn remove(&mut self, i: usize) {
      self.children.remove(i);
    }

    fn insert(&mut self, i: usize, c: StrT) {
      self.children.insert(i, c);
    }
  }

  //////////////////////////////////////////////////////////////////////////////////////////////////

  #[test]
  fn test_impose_frag_mut_underlying() {
    let mut u = tree("1()");
    Live::Frag.impose(virt("2()"), &mut u);
    assert_eq!(u, tree("2()"));
  }

  #[test]
  fn test_impose_new_branch() {
    let mut l = live("*");
    let mut u = tree("alt()");
    l.impose(virt("3(1()2())"), &mut u);
    assert_eq!(u, tree("3(1()2())"));
  }

  #[test]
  fn test_impose_update_spine() {
    let mut l = live("1()");
    let mut u = tree("1()");
    l.impose(virt("2()"), &mut u);
    assert_eq!(l, *live("2()").incr_counter());
    assert_eq!(u, tree("2()"));
  }

  #[test]
  fn test_impose_add_arm() {
    let mut l = live("4()");
    let mut u = tree("4()");
    l.impose(Virt::Branch(
      Branch { spine: "4".into(), arms: vec![Virt::Frag(tree("alt()"))] },
      ()
    ), &mut u);
    assert_eq!(l, *live("4(*)").incr_counter());
    assert_eq!(u, tree("4(alt())"));
  }

  #[test]
  fn test_impose_remove_arm() {
    let mut l = live("4(*)");
    let mut u = tree("4(alt())");
    l.impose(virt("4()"), &mut u);
    assert_eq!(l, *live("4()").incr_counter());
    assert_eq!(u, tree("4()"));
  }

  #[test]
  fn test_impose_update_child() {
    let mut l = live("4(3())");
    let mut u = tree("4(3())");
    l.impose(virt("4(2())"), &mut u);
    assert_eq!(l, *live("4(2())").incr_counter());
    assert_eq!(u, tree("4(2())"));
  }

  #[test]
  fn test_impose_rec_update_no_changes() {
    let mut l = live("4(3())");
    let mut u = tree("4(3())");
    l.impose(virt("4(3())"), &mut u);
    assert_eq!(l,
               Live::Branch(Branch {
                 spine: "4".into(),
                 arms: vec![Live::Branch(Branch {
                   spine: "3".into(),
                   arms: vec![],
                 }, 1)],
               }, 1));
    assert_eq!(u, tree("4(3())"));
  }
}

////////////////////////////////////////////////////////////////////////////////////////////////////
// Public API

#[derive(Eq, PartialEq)]
pub struct Tree<U: Underlying> {
  pub underlying: U,
  live: Live<U>,
}

#[repr(transparent)]
pub struct Virtual<U: Underlying>(Virt<U>);

impl<U: Underlying> From<U> for Tree<U> {
  fn from(underlying: U) -> Self {
    Tree {
      underlying,
      live: Live::Frag,
    }
  }
}

impl<U: Underlying + Default> Default for Tree<U> {
  fn default() -> Self {
    U::default().into()
  }
}

impl<U: Underlying> Tree<U> {
  pub fn impose(&mut self, virtual_tree: Virtual<U>) {
    self.live.impose(virtual_tree.0, &mut self.underlying);
  }
}

impl<U: Underlying> From<U> for Virtual<U> {
  fn from(u: U) -> Self {
    Virtual(Virt::Frag(u))
  }
}

impl<U: Underlying + Default> Default for Virtual<U> {
  fn default() -> Self {
    U::default().into()
  }
}

impl<U> Clone for Virtual<U>
where U: Underlying + Clone, U::Info: Clone {
  fn clone(&self) -> Self {
    Virtual(self.0.clone())
  }
}

impl<U: Underlying> Virtual<U> {
  pub fn frag(frg: U) -> Self {
    frg.into()
  }

  pub fn branch(spine: U::Spine,
                info: U::Info,
                arms: Vec<Virtual<U>>) -> Self {
    use std;
    let arms: Vec<Virt<U>> = unsafe {
      std::mem::transmute(arms) // safe because its a transparent newtype
    };
    Virtual(Virt::Branch(Branch { spine, arms }, info))
  }
}
